package ZS1;

import java.util.Arrays;

/**
 * 乘积最大子数组
 * 给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），
 * 并返回该子数组所对应的乘积。
 * 输入: [2,3,-2,4]
 * 输出: 6
 * 解释: 子数组 [2,3] 有最大乘积 6。
 */
public class Main6 {
    public static void main(String[] args) {
        int[] arr = {2,3,-2,4};
        System.out.println(maxProduct2(arr));
    }

    public static int maxProduct(int[] nums) {
        int n = nums.length;
        int[] maxDP = new int[n];
        int[] minDP = new int[n];
        maxDP[0] = nums[0];
        minDP[0] = nums[0];

        for (int i = 1; i < n; i++) {
            maxDP[i] = Math.max(nums[i],Math.max(maxDP[i-1]*nums[i],minDP[i]*nums[i-1]));
            minDP[i] = Math.min(nums[i],Math.min(maxDP[i-1]*nums[i],minDP[i]*nums[i-1]));
        }
        Arrays.sort(maxDP);
        return maxDP[n-1];
    }

    public static int maxProduct2(int[] nums){
        int imin = 1;
        int imax = 1;
        int max_val = Integer.MIN_VALUE;

        for (int i = 0; i < nums.length; i++) {
            if(nums[i]<0){
                int temp = imax;
                imax = imin;
                imin = temp;
            }
            imax = Math.max(imax*nums[i],nums[i]);
            imin = Math.min(imin*nums[i],nums[i]);

            max_val = Math.max(imax,max_val);
        }
        return max_val;
    }

}
